The government of the United States of America has a non-exclusive license in this invention pursuant to United States Air Force contract No. F49620-92-C-0062.
The present invention relates generally to broadband data switching networks, and more specifically to optoelectronic banyan switching networks for increasing the efficiency and decreasing the cost of signal switching in a broadband system.
There is an ever-increasing demand for high throughput, cost effective, broadband data switching networks as demonstrated by the explosive growth in the Asynchronous Transfer Mode (ATM) equipment industry. Future switching networks must handle thousands of high bandwidth channels, implying an aggregate capacity for networks in the regime of terabits per second. These requirements exceed the ability of VLSI-based switching technology.
One proposal to meet this high throughput demand involves the use of a self-routing, banyan-based network which uses a deflection algorithm to route packets efficiently to their destinations while minimizing resources for a given blocking rate. In particular, one implementation, the tandem banyan switch, has been proposed. A 2-shuffle tandem banyan switching network is made up of a plurality of banyans all connected consecutively. Each banyan has N signal inputs, N signal outputs and log.sub.2 N stages, where N is a power of two. Each of the log.sub.2 N stages comprise (N/2) 2.times.2 switching elements, each with two signal inputs and two signal outputs, and any switching logic required to properly route signals through the stage. The individual stages, therefore, also have N inputs and N outputs. The N inputs of the first stage serve as the N inputs for the banyan and the N outputs of the final stage serve as the N outputs of the banyan. The remaining inputs and outputs are connected consecutively to each other, the outputs of the i.sup.th stage being connected to the inputs of the (i +1).sup.th stage. The switching elements in the stages allow an input signal to pass to either of the two switch outputs depending upon the switching element's control logic and a destination address contained in the signal. The inputs and outputs of the various stages are connected in such a way that there is a unique path through the banyan from any of the N inputs to any of the N outputs. The network is called a 2-shuffle because it uses switches with 2 inputs connected to two possible outputs (2.times.2 switch).
The particular configurations of the connections between the stages in a banyan may vary depending upon the needs of the system. Three possible banyan designs including different connections are disclosed in Architecture, Performance and Implementation of the Tandem Banyan Fast Packet Switch by Tobagi et al., IEEE Journal on Selected Areas in Communications, Vol. 9, No. 8, October 1991, pp. 1173-1193. In particular, Tobagi discloses on page 1175 the connections for a baseline network, a modified data manipulator, and an omega network. Illustrations of the connections for these three banyan networks are shown respectively in FIGS. 1A-1C. As these drawings illustrate, the connections between the stages of a banyan may be identical as in FIG. 1C, or may differ among stages as in FIGS. 1A and 1B.
Although each of the connections shown in FIGS. 1A-1C show a 2-shuffle connection, with the stages being made up of 2.times.2 switches, other connections are possible for other shuffle sizes. In general, a banyan having N inputs and N outputs is implemented with a k-shuffle by using log.sub.k N stages comprising k .times.k switches. As with a 2-shuffle, the k.times.k switches in the stages of a k-shuffle are connected in such a way that there is a unique path through the banyan from any of the N inputs to any of the N outputs.
The signals passing through the banyan are often self-routing. This means that at each stage of the banyan, the switching logic can route the signal without any additional information beyond that contained in the signal. Self-routing signals contain a header with destination data indicating the destination address. Usually these destination data include the binary coded decimal address of the destination. One method by which self-routing is accomplished involves routing the signal at each stage according to a different bit in the destination address. Generally, the bit used for routing corresponds to the order of the stage that the signal is in, i.e., the first bit of the address is used for routing in the first stage, the second bit is used in the second stage, and so forth.
An example of self-routing in the omega network banyan shown in FIG. 1C will be explained with reference to FIG. 2. In FIG. 2, the banyan has sixteen inputs and four stages, each switching stage comprising eight 2.times.2 switches. The input and output nodes of the banyan are labeled in binary coded decimal from 0000-1111 (0-15) and correspond to the input address and output address, respectively. At each stage, the switching logic and the switches route the signal according to a bit in the signal's destination address corresponding to the order of the current stage. The switches route the signal low if the bit is a logical "1" and high if the signal is a logical "0".
In the example illustrated by FIG. 2, the signal has an input address of 0010, and a destination address of 1011. The heavy line in FIG. 2 shows the passage of the signal through the four stages of the banyan. Upon entry into the banyan, the signal is routed to the fifth node of the first stage, i.e., the top input of the third 2.times.2 switch from the top in the first stage. This initial routing depends entirely upon the signal's input address and may vary among the any of the inputs to the banyan without affecting its routing performance. In the first stage, the switch routes the signal based on the first bit in its destination address. In this example, the first bit of the destination address is "1", so the switch routes the signal through the low output of the switch. Similarly, the switches in the second through fourth stages route the signal according to the second through fourth bits of the destination address, high, low, and low, respectively, arriving correctly at output address 1011.
Although the signal in this example started at input address 0010, the starting address is irrelevant to the routing. The signal could start at any of the sixteen input addresses and, by branching at each stage according to the corresponding bit in the destination address, would arrive at the correct output address. This input irrelevance occurs because the connections between the switches in the various stages are made such that there is a unique path from each input to each output.
The connection used between stages in the omega network banyan is called a perfect shuffle (PS). A PS is performed on a one-dimensional (1-D) array by interleaving the elements of the first half of the array with those of the second half, with the first and last elements remaining unchanged in their positions. For example, the PS of the eight-element array {1, 2, 3, 4, 5, 6, 7, 8} is {1, 5, 2, 6, 3, 7, 4, 8}. The connections between the stages in FIGS. 1C and 2 show PS connections for a sixteen-element array. A further discussion of the PS appears in "Parallel Processing with the Perfect Shuffle" by H. Stone, IEEE Trans. Comput., C-20, 153 (1973).
A tandem banyan network using PS connections is shown in FIG. 3. The three banyans shown are connected together by a PS connection. Within each banyan, every stage is connected to the next stage by a PS connection. The PS connections in each stage are coupled to an array of 2.times.2 switches to route the signals to the next stage. In a PS-based tandem banyan network, each stage and therefore each banyan is identical. A PS-based banyan can perform arbitrary permutations of the elements in interconnection networks for applications such as routing and sorting.
In a banyan, a signal is input at each stage to one of the N/2 switches and is output from one of the two outputs of that switch. For all but the final stage, this output is directly connected to the input of one of the switches in the next stage. The connections between the stages are designed so that by passing through the entire banyan, a signal can travel from any one of the N inputs to any one of the N outputs by a unique path. The routing of a signal through the banyan is generally implemented through the use of a destination address having log.sub.2 N bits. As the signal passes through each stage of the banyan, the banyan control logic examines the corresponding bit in the destination address to determine how the signal should branch from the switch to which it is input in that stage.
This approach would allow for perfect routing of the N signals through a single banyan with log.sub.2 N stages if no two signals were ever simultaneously routed to the same output of a given switch in a particular stage. Unfortunately, given the realities of signal routing, this is not the case. As multiple signals pass through the banyan, collisions between two of the signals inevitably occur. In order to preserve the functioning of the system, when the network determines that a collision will occur, it avoids the actual collision by allowing one of the signals to succeed and continue through to the next stage via the desired output, and causing the remaining signal to fail and proceed to the next stage via the other output of the 2.times.2 switch.
The signals that fail in one stage of an individual banyan are treated as automatically failing signals in any later stages in the banyan. These automatically-failing signals defer in any further collisions to signals that have only been successfully routed in previous stages. At the end of the first banyan in the tandem banyan network, the signals that have passed through all of the stages of the banyan with no collisions or with only successful collisions are routed to the output of the tandem banyan network. All failing signals have their failure status removed and are routed to the beginning of the second banyan.
This second banyan is constructed and operates identically to the first banyan. However, since the second banyan only accepts as inputs the signals that failed passing through the first banyan, fewer signals must pass through the second banyan and so fewer collisions are likely to occur during signal routing. A third identical banyan is in turn connected to the end of the second banyan to process any failed signals from the second banyan, and so on until the probability of a collision occurring in the banyan drops to an acceptably low value. Computer simulations predict that for a 4-shuffle tandem banyan network with 1024 inputs to achieve a probability of collision (also called blocking probability) of 10.sup.-6 it would require 40 stages or eight banyans. This can be seen in Optical Freespace Sliding Tandem Banyan Architecture for Self-routing Switching Networks, by Michael W. Haney and Marc P. Christensen, Technical Digest of the International Conference on Optical Computing, Edinburgh, Scotland, Aug. 22-25, 1994.
As noted above, the signals passing through the tandem banyan network are often self-routing. A standard tandem banyan network for use with self-routing signals requires that the header include both the destination address and a conflict bit to determine if the packet has been misrouted, i.e., whether a collision has occurred. This conflict bit will be initially set to indicate no conflict, but will be changed for the duration of a banyan if an unsuccessful collision occurs. In some implementations of the tandem banyan network, the destination addresses will be rotated by one bit in each stage as it is routed, so that the next stage need only inspect the first address bit to determine the how to perform the switching.
The tandem banyan network contains some inherent inefficiencies, however. Any routing steps performed on a failed signal are lost time and effort. Unfortunately, since a signal's failed status can only be removed at the end of a banyan, any signals that fail prior to the final stage of a banyan must pass through more than one stage as a failed signal. In a worst case, a collision will occur in the first stage of a banyan. When this happens, the failed signal must idly pass through all the remaining stages of the banyan before it can meaningfully resume its self-routing at the start of a new banyan.
This problem occurs because signals in the tandem banyan network can only be output, and thus removed from contention for signal lines in the network, when they have passed through an entire banyan successfully. If a signal fails in just one stage in a banyan, it no longer meets this criterion and must wait until the next banyan to try again.
In addition to the problem of wasted time and routing efforts, the tandem banyan encounters problems with power consumption. As the number of stages in the tandem banyan network increases, so to does its power consumption. As shown in FIG. 3, at the end of each banyan in the network, the N outputs of the banyan are each connected to the N outputs of the network by connecting signal lines. These lines allow signals that have been successfully routed in a particular banyan to exit the network. Each of these connecting signal lines requires a line driver, however, and each line driver requires a discrete amount of power. For networks with a large value for N, the power consumption of these line drivers can become high since each additional banyan requires N additional line drivers. A tandem banyan with 5 banyans and N=1024, for example, would require 5,120 line drivers as well as additional logic to direct the 5,120 output lines. If each of the line drivers only requires about 10 mW of power, just the drivers for the removal of data from the network in the network will require over 50 W of power.